Devices that use TCP (Transmission Control Protocol) for transmitting and receiving data are now commonly employed. TCP is a protocol used under the OSI (Open Systems Interconnection) Reference Model, and is used when data streamed from an upper layer are divided into data segments for transmission from a sender device to a receiver device. TCP ensures reliable streaming of ordered data segments to a receiver device. Specifically, a number (hereinafter referred to as “a sequence number”) is allocated to each data segment in a data sequence to indicate an order of the data segment in the data sequence. A sender device allocates a sequence number to a header of each data segment to be transmitted, and also initializes a timer when the data segment is transmitted. If there is no acknowledgement from the receiver device of receipt of a transmitted data segment within a projected time (Timeout), the time being determined on the basis of an estimated time for transmission of the data segment to its reception, and acknowledgement of its receipt (i.e., estimated round trip time of the data segment), the sender device tentatively determines that the data segment has been lost without reaching the receiver device and retransmits the data segment to the receiver device.
At a sender device, when an acknowledgement is received, a number contained in a header of the received acknowledgement indicates which data segment the received acknowledgement corresponds to. When the receiver device transmits an acknowledgement it sets a sequence number of a data segment which it expects to receive next in the “acknowledgement number” field in the header of the acknowledgement. For instance, when using sequence numbers starting from 500 and followed by 1000, 1500 etc., an acknowledgement number of an acknowledgement to be transmitted to a sender device is set as 1000 once a data segment having a sequence number “500” is received. Upon receiving such an acknowledgment, the sender device determines that a transmitted data segment has been safely received by a receiver device and transmits a subsequent data segment.
It is to be noted that a sender device receives an acknowledgment having an acknowledgment number 1000 where the sender device has not transmitted a data segment having a sequence number 1000, or where even if the data segment has been transmitted, the segment has not been received by a receiver device. This acknowledgement number remains set at 1000 until a data segment containing a sequence number 1000 is received at the receiver device even where a subsequent data segment having a sequence number 1500 is already received at a receiver device due to a loss of the data segment having a sequence number 1000. Thus, a sequence number of the least recent data segment which is not received by a receiver device is set as an acknowledgement number.
In the data segment transmission method explained above, reliability is ensured by transmitting from a sender device a subsequent data segment only after receipt at the device from a receiver device of an acknowledgement for a previously transmitted data segment. However, while this method ensures data transmission reliability it inhibits efficiency. To improve efficiency, TCP provides a method for transmitting a certain number of data segments according to a number defined by a “window.” A “window” is a number of bytes or a number of data segments that can be transmitted prior to receipt of an acknowledgement. A window size is determined by a sender device such that it does not exceed an available buffer size of a receiver device. When a sender device receives an acknowledgement for a transmitted data segment(s), a window slides by the number of data segments for which an acknowledgement has been received, and a subsequent data segment(s) is transmitted to the extent by which a window has slid. This method is referred to as a “sliding window method”; and by controlling a window size, a data flow is controlled.
If data flow is suspended when a sliding window method is being employed, due to, for example, a break in wireless communication or congestion in a system, transmitted data segments may either be lost in the system or need to be stored temporarily in a node in the network until data communication is restored. Especially, deterioration is more likely to happen in a wireless communication environment. Following restoration of data communication, any data segments that are temporarily stored in a node in the network are able to reach the receiver device, although with some delay.
However, if communication disruption persists for a relatively long time, and a timeout occurs at a sender device for a transmitted data segment, the sender device retransmits a first data segment from among data segments that have thus far been transmitted but that have not been acknowledged. As a result, the receiver device receives both the data segment temporarily stored in the network (hereinafter referred to as “an original data segment”) and the retransmitted data segment. The receiver device then returns an acknowledgement for the original data segment upon its receipt, and also transmits an acknowledgement for the retransmitted data segment upon its receipt; with each of these acknowledgments normally having the same acknowledgment number. This gives rise to a problem that the sender device is unable to determine whether an acknowledgment received pertains to an originally transmitted or to a retransmitted data segment, and reverts to a state where it is determined that the original data segment failed to reach the receiver device.
In the following two examples, explanation will be given for such a situation.
FIG. 10 is an example sequence diagram showing a case where a packet communication is performed between a server device 10′ (a sender device) and a client device 50 (a receiver device). A 4-digit-number appearing to the right of an initial point of each arrow at server device 10′ in the figure is a sequence number of a data segment transmitted from server device 10′; and a 4-digit-number appearing to the left of an initial point of each arrow at receiver device 50 in the figure is an acknowledgement number included in an acknowledgement transmitted from client device 50. It is assumed here that an original sliding window size is three, i.e., three data segments may be sent without receiving an acknowledgement.
In FIG. 10, three data segments (original data segments) S1-S3 are transmitted for a first time from server device 10′, the data segments S1, S2, and S3 having sequence numbers 0, 1000, and 2000, respectively. A timer is set at server device 10′ upon transmission of the data segments.
In the figure, the data segments S1, S2, and S3 are received at client device 50 with a delay due to deterioration in network communication conditions. Client device 50, upon receiving the original data segment S1, transmits to server device 10′ an acknowledgement RI having acknowledgment number 1000. Likewise, upon receiving original data segment S2, client device 50 transmits an acknowledgement R2 having acknowledgment number 2000, and an acknowledgement R3 having acknowledgment number 3000 upon receiving original data segment S3.
As shown in the figure, server device 10′ does not receive an acknowledgment from receiver device 50 before an elapsed time measured by a timer exceeds a timeout value. As a result, server device 10′ determines that the original data segment S1 has not been received by client device 50 at the time of timeout, and retransmits a data segment having sequence number 0 (retransmitted data segment S′1). One data segment, i.e., retransmitted data segment S′1, is transmitted here because a window size is reduced to a minimum value upon timeout.
Server device 10′ subsequently receives an acknowledgement R1 having an acknowledgement number 1000. Here, server device 10′ is unable to determine on the basis of the acknowledgement number 1000 whether the acknowledgement R1 pertains to original data segment S1 or to retransmitted data segment S′1, for the reason stated above. Therefore, server device 10′ treats acknowledgement R1 as pertaining to retransmitted data segment S′1, and a data segment having sequence number 1000 is therefore retransmitted (retransmitted data segment S′2). Server device 10′ further retransmits a data segment having a subsequent sequence number 2000 (retransmitted data segment S′3) because the window size is increased by one after receiving the acknowledgement R1.
Server device 10′ subsequently receives an acknowledgement R2 having an acknowledgement number 2000, and subsequent original data segments (original data segment S4 and following original data segments) are sequentially transmitted.
In the example, original data segments S2 and S3 are retransmitted (retransmitted data segments S′2 and S′3) even though they have safely arrived at client device 50. That is, when data segments S2 and S3 are each received by client device 50 at two different times, the retransmission of data segments S2 and S3 results in unnecessary transmission, although this was not determined at the time of the retransmission. Further, as is clear from FIG. 10, acknowledgements R′2 and R′3 are also transmitted in response to the retransmitted data segments S′2 and S′3. Thus, a total of four data segments are unnecessarily retransmitted.
FIG. 11 shows a second example of where unnecessary retransmission of data segments may take place. To prevent a receiver device from transmitting an excessive number of acknowledgements, TCP provides that transmission of an acknowledgement from a receiver device may be delayed within a prescribed time, and that the acknowledgement may be transmitted together with a next data transmission from the receiver device (“Delayed Acknowledgement”, RFC 2581). However, in a case of receiving two full-size data segments in a row within a prescribed time, an acknowledgement should be transmitted without waiting for a next data transmission. That is, in a case that two data segments are received within a short time lag, for example within 200 msec (millisecond) of each other, an acknowledgement informing receipt of the two data segments can be substituted by use of a single acknowledgement. Specifically, a receiver device transmits an acknowledgement for the second received data segment thereby informing a sender device of receipt of the two data segments. This is the case in the example shown in FIG. 11.
In FIG. 11, the original data segments S1, S2, and S3 are transmitted from server device 10′ and received subsequently by client device 50 with some delay due to deterioration in the communication path, as assumed in the case of FIG. 10. Subsequently, client device 50 transmits an acknowledgement R2. In the meantime, server device 10′ retransmits data segment S1 (retransmitted data segment S′1) due to the timeout. One data segment, i.e., retransmitted data segment S′1, is transmitted here because a window size is reduced to a minimum value upon timeout.
Server device 10′ subsequently receives the acknowledgement R2 transmitted from client device 50. Upon receipt, server device 10′ refers to acknowledgement number 2000 contained in acknowledgement R2, and retransmits a segment having the same sequence number, i.e., the original data segment S3. Server device 10′ further transmits a subsequent original data segment S4 having sequence number 3000 because the window size is increased by one data segment by receiving the acknowledgement R2.
Server device 10′ subsequently receives an acknowledgement R3 having acknowledgement number 3000 transmitted from client device 50. As a result, server device 10′ sequentially transmits an original data segment S5 having a subsequent sequence number 4000 and following data segments.
In this example, the original data segment S3 is retransmitted even though the segment S3 has been safely received by client device 50 in actuality; and as shown in FIG. 11 an acknowledgement R′3 for the retransmitted data segment S′3 is also transmitted. Thus, the retransmission of data segment S′3 and the acknowledgement R′3 constitute unnecessary transmission.
Such unnecessary transmission of data segments is not performed if it is determined that an acknowledgement received after retransmission of a data segment pertains to an original data segment in a case where a sender device is unable to determine whether the acknowledgement pertains to the original data segment or the retransmitted data segment.
However, when such a determination is made, an acknowledgment for a retransmitted data segment is regarded as an acknowledgement for an original data segment, wherein a window is slid forwards, causing a subsequent original data segment to be transmitted. When such a transmission of an original data segment is repeated, there is a risk of a cumulative increase in the number of data segments that have been transmitted from server device 10′ but that have not reached client device 50 being increased.
To avoid such a risk, it is determined by default that an acknowledgement pertains to an original data segment in a case where a sender device is unable to determine whether the acknowledgement pertains to the original data segment or a retransmitted data segment. However, using this determination, a sender device is unable to avoid unnecessary retransmission of a data segment.
To solve this problem, “The Eifel Detection Algorithm for TCP” (Reiner Ludwig, et. al, http://www.watersprings.org/pub/id/draft-ietf-tsvwg-tcp-eifel-alg-04.txt, 24 Jul., 2002) discloses a technique for enabling reliable determination as to whether an acknowledgment pertains to an original data segment or to a retransmitted data segment by using the TCP Time Stamps Option defined in RFC 1323.
Also, in “On Estimating End-To-End Network Path Properties. 2.8 Impact of Bad Timeouts” (Mark Allman, Vern Paxson, ACM SIGCOMM '99, vol.29, no.4, pp 263-274, Oct. 1999), Allman et. al proposes a technique for using statistical information to estimate whether a received acknowledgment pertains to an original data segment or to a retransmitted data segment in packet communication in a wired packet communication network.
In the Allman's proposal, estimation is performed on the basis of ½ of a minimum round trip time as a threshold value, where the minimum round trip time is the smallest value of a plurality of round trip times obtained by measuring a time from which a data segment is transmitted until a time when an acknowledgment for the segment is received while a connection remains alive between a sender device and a receiver device. In the method, if a time which elapses from retransmission of a data segment until a time when a first acknowledgement is received is equal to or longer than (or longer than) the threshold value, the acknowledgement received is regarded as pertaining to the retransmitted data segment, with the elapsed time being less than (or equal to or less than) the threshold value, while the acknowledgment received is regarded as pertaining to the original data segment.
Determination of the threshold time as being a half that of a minimum round trip time is based on the following conditions:
1. Statistically, a probability of an acknowledgement being received for an originally transmitted data segment is about the same during: a period from retransmission until ½ of a minimum round trip time has elapsed; a period from retransmission until ¾ of a minimum round trip time has elapsed; and a period from retransmission until the complete minimum round trip time has elapsed; and
2. Statistically, a probability of receiving an acknowledgement for a retransmitted data segment sharply increases about a time point shortly after ½ of the minimum round trip time has elapsed from retransmission.
However, when the Eifel Detection Algorithm is used, time stamp information is always appended to an original data segment at a sender device and to an acknowledgement at a receiver device even under good network conditions. This means that the size of both the original data segment and the acknowledgement data segment is increased. The increase in the amount of transmitted data leads to an increase in communication charges where subscribers are charged for communication in proportion to the amount of segments transmitted through a network. Such an undesirable increase in communication charges is likely to become more pronounced where network conditions are good and instances of data retransmission are likely to be small. Clearly, such increases in communication charges are not desirable for users of receiver devices or sender devices.
It is feasible to include time stamp information in reserved bits of a TCP header used at the time of communication instead of adding the information to a data segment. However, existing communication systems do not support such a method, and consequently, sender and receiver devices would need to be significantly modified to employ such a method.
Further, even when the technique of Allman is used, an optimum result of the determination cannot be obtained in a mobile communication environment where data segment delay is pronounced in a wireless section.